10539. Почти простые числа

Натуральное число называется почти простым, если оно не простое и имеет только один простой делитель. Найти количество почти простых чисел в заданном интервале натуральных чисел.

Вход. Первая строка содержит количество тестов n (n £ 600). Каждая следующая строка является отдельным тестом и содержит два числа low и high (0 < low £ high < 10¹²).

Выход. Для каждого теста вывести в отдельной строке количество почти простых чисел в промежутке [low.. high] включительно.

Пример входа

3
1 10
1 20
1 5

Пример выхода

3
4
1

РЕШЕНИЕ

решето Эратосфена - бинарный поиск

Анализ алгоритма

Почти простые числа имеют вид p^k, где p – простое число, k ³ 2. Например, почти простыми будут 4, 8, 16, 32, 9, 81, … . Поскольку high < 10¹², то исходя из определения почти простого числа p < 10⁶. Сгенерируем массив primes длины 1000000 = 10⁶, для которого primes[i] = 1 если i – простое число и primes[i] = 0 иначе. Далее сгенерируем и отсортируем в массиве m все почти простые числа (их будет 80071). Обозначим через f(a, b) количество почти простых чисел в промежутке [a..b]. Тогда f(low, high) = f(1, high) - f(1, low - 1). Количество почти простых чисел на промежутке [1 .. n] равно номеру места (индексу), куда можно вставить число n в отсортированный массив m по верхней границе с учетом сохранения упорядоченности. Номер индекса ищется бинарным поиском по массиву m при помощи функции upper_bound.

Пример

Рассмотрим второй тест. От 1 до 20 находится 4 почти простых числа: 4, 8, 9, 16.

Реализация алгоритма

Сгенерируем массив primes для тестирования чисел на простоту.

void gen_primes(void)

{

int i, j;

for(i = 0;i < MAX; i++) primes[i] = 1;

for(i = 2; i <= (int)sqrt(1.0*MAX); i++)

if (primes[i])

for(j = i * i; j < MAX; j += i) primes[j] = 0;

}

Для каждого простого числа i заносим в массив m числа i², i³, i⁴, … пока очередная степень не станет больше 10¹². Переменная ptr содержит индекс последнего почти простого числа, занесенного в массив m. Поскольку почти простые числа ограничены значением 10¹², то работать следует с 64 битовыми целыми числами (тип long long). Последним числом в массиве m поставим любое число, большее 10¹². Пусть им будет 10¹² + 1. Это следует сделать для корректной работы последующей функции бинарного поиска.

ptr = -1;

for (i = 2; i < MAX; i++)

if (primes[i])

{

temp = i;

while ((temp *= i) < 1e12)

m[++ptr] = temp;

}

m[++ptr] = 1e12 + 1;

Сортируем массив m, используя STL:

sort(m,m+ptr);

Читаем количество входных тестов n и для каждого интервала [a, b] вычисляем и выводим значение f(a, b) = f(1, b) – f(1, a – 1) за константное время.

scanf("%d",&n);

for(test = 1; test <= n; test++)

{

scanf("%lld %lld",&a,&b);

printf("%d\n",upper_bound(m,m+ptr,b) - upper_bound(m,m+ptr,a-1));

}